The use of data networks for the reliable high speed transport of information, such as text, voice, video, etc., over wide areas in digital format via a variety of media including optical fibers is bringing major changes to network services and network architecture/infrastructure design. Many new services having diverse characteristics and bandwidth requirements are now feasible. One emerging example of such data networks is Broadband ISDN (BISDN), which is designed to support a variety of applications such as interactive and distributed audio, video and data communications. The principal transfer mode for BISDN is called Asynchronous Transfer Mode (ATM). ATM is a high-bandwidth, low delay, packet-like switching and multiplexing technique. See, S. E. Minzer, "Broadband ISDN and Asynchronous Transfer Mode," IEEE Comm. Mag., pp. 17-24, September 1989.
FIG. 1A illustrates a typical high speed network 100 comprising switching nodes 106-i connected by high-bandwidth data links 108-j. Inputs to the network 100 are from user locations 101-k, k=1, 2, . . . , NS. These inputs may be of any form, but are conveniently formatted at the user locations into fixed-length packets or cells (the terms will be used interchangeably in the sequel) for transmission to other user locations or to gateway or inter-network nodes 110, which nodes are from a user location 101-k is not in the proper form, switching nodes 106-i are arranged to appropriately format the input data. Communication between user location 101-k (or between a user location and an off-network location, e.g., via link 112) is advantageously via virtual circuits, as is well known in the art.
It proves convenient to associate a so-called "window" with each virtual circuit, which window represents the total number of cells in transit through the virtual circuit at any time. In some networks many cells may be in transit between an originating node, e.g., 106-1 and a terminating node, e.g., 106-2 in FIG. 1A. The in-transit cells may be propagating through a link 106-i, or they may be temporarily queued at one of the nodes along the path of the virtual circuit. Thus the windo size, conveniently identified by the value K (in units of packets or cells), may be fairly large.
Some networks use explicit acknowledgement signals from the terminating node of a virtual circuit back to the originating node of a virtual circuit to indicate the error-free reception of packet or cell. Such acknowledgement signals can then be used to advance the window, thereby admitting a new cell into the virtual circuit. Conversely, when congestion is indicated, e.g., by a feedback signal from a downstream node, or when an error is detected requiring a retransmission between links in the network, the window can shrink or remain stationary. Variants of such "flow control" in the face of errors or congestion are known in the art.
The afore-mentioned queues, when needed, are typically implemented using buffer memory at each node along a virtual circuit. These buffers may be shared, as is typical for the so-called first-come-first-served (FCFS) service discipline, or they may be provided on a per-virtual-circuit basis when using a service discipline such as a round-robin (including weighted round-robin, WRR) discipline. The service discipline, in any event, allocates available node output capacity (e.g., trunk bandwidth) to meet the competing service requirements for each virtual circuit. It sometimes proves advantageous to allocate available bandwidth in light of the nature of the data sources, e.g., giving one class of service for relatively short, bursty inputs and another class of service to virtual circuits carrying large file transfers. In high speed networks, the very great amount of data flowing requires that buffering, allocating and other control functions be performed in a very rapid fashion. It is therefore very important that these functions be performed with minimum complexity.
Some data services are based on an agreed-upon grade of service. For example, a service provider and a user may agree that each virtual circuit (VC) is to have a "Committed Information Rate (CIR)." Thus a quiescent user seeking to start up or commence sending data over a VC expects to receive at least its CIR almost immediately. A number of techniques have been developed to help ensure that competing demands for service are handled in such manner as to minimize congestion and avoid loss of data transmitted within the agreed-upon CIR. See, e.g., U.S. Pat. Nos. 4,769,810 and 4,769,811 issued to Eckberg, et al on Sep. 6, 1988. Congestion control techniques are discussed generally in U.S. Pat. No. 5,014,265 issued May 7, 1991 to Hahne, et al, and in Tanenbaum, Computer Networks, 2nd Ed., Prentice Hall (1988), pp. 223-239, 287-288 and 309-322.
Advantageously, an Admission Controller is used to restrict the total number of VCs at each node, and to monitor the sum of CIRs, for the VCs that have been admitted, to the total bandwidth. See "Performance Evaluation and Design of Multiservice Networks," J. W. Roberts, Ed. Final Report of the Cost 224 Project, Commission of the European Communities (1992); R. Guerin, H. Ahmadi and M. Naghshineh, "Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks," IEEE J. Selected Areas Comm., vol. 9, pp. 968-981 (1991); A. Elwalid and D. Mitra, "Effective Bandwidth of General Markovian Traffic Sources and Admission Control of High Speed Networks," IEEE INFOCOM'93, pp. 256-264 (1993). It is generally desirable that the network control be responsive in providing "bandwidth on demand" to any VC, even if the amount required is in excess of its CIR, provided of course that this can be done while meeting contractual obligations to all VCs which are on at the time.
Fairness is a major goal of feedback-based congestion control. Such fairness typically encompasses several aspects. A first is that a VC should receive at least its CIR at any time it is required. This implies that when a VC turns on from a quiescent state, the network must respond speedily. Second, it is common for a VC to require bandwidth in excess of its CIR. Moreover, given the bursty nature of many sources, it is quite typical for the network to have bandwidth in excess of the sum of the CIRs of the active VCs. Such excess bandwidth is desirably made available to requesting VCs in a rational way, e.g., in proportion to their CIRs. A final desiderata is that fairness hold not only over long time periods, but also over relatively short time periods. "Best Effort" service, wherein the network makes no guarantees but attempts to make bandwidth available fairly, is the particular case of the above in which the CIRs are set to zero.
Feedback can be used to regulate both rates of admission of new data onto the network and window size, so as to respond to demands for bandwidth in an efficient and fair manner. Rates and windows are related in several major respects. In window-based control, a natural rate is the throughput, measured in packets per unit time. In wide area, high-speed networks, the throughput is close to the window size (in packets) per round-trip propagation delay over a broad range of practical operating conditions. This simple relation is the bridge between the two quantities, and thus methods for adapting rates based on feedback are in one-to-one correspondence with methods for adapting windows.
Traffic management and congestion control design of these high speed, wide area networks to ensure efficient bandwidth utilization, bandwidth availability and fairness among users has proved challenging. Some key issues or criteria in evaluating the effectiveness of network traffic management and congestion control methods include: 1) fairness in short and long term behavior among VCs in competing for bandwidth, 2) the effect of large amplitude oscillations in network behavior caused by delayed feedback, 3) transient behavior, i.e. the quality of the responsiveness in a dynamic environment, 4) the ability to arbitrarily allocate bandwidth to different VCs as is typically required, 5) dealing with various propagation delays in the network which sometimes tend to discriminate against VCs on longer paths, 6) fulfilling contractual guarantees from the network to the user and 7) robustness of the design process in terms of network performance sensitivity to parameter values. K. K. Ramakrishnan and R. Jain, "A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer," Proc. ACM SIGCOMM, pp. 303-313 (1988); V. Jacobson, " Congestion Avoidance and Control," Proc. ACM SIGCOMM, pp. 314-329 (1988).
Traffic on the network may be controlled by a variety of methods, e.g. by regulating the admission of new data onto the network, by regulating the window size, etc. See generally, I. W. Habib and T. N. Saadawi, "Controlling Flow and Avoiding Congestion in Broadband Networks," IEEE Comm. Mag., pp. 46-53, October 1991; H. Gilbert, O. Aboul-Magd and V. Phung, "Developing a Cohesive Traffic Management Strategy for ATM Networks," IEEE Comm. Mag., pp. 36-45, October 1991; A. E. Eckberg, B. T. Doshi and R. Zoccolillo, "Controlling Congestion in B-ISDN/ATM: Issues and Strategies," IEEE Comm. Mag., pp. 64-70, September 1991; J. W. Roberts, "Variable-Bit-Rate Traffic Control in B-ISDN," IEEE Comm. Mag., pp. 50-56, September 1991; D. Hong, and T. Suda, "Congestion Control and Prevention in ATM Networks," IEEE Network Mag., pp. 10-16, July 1991. However, any management or congestion control scheme must contend with the physical limitations of the network. In particular, propagation delays (a consequence of the physical area served by the network and the finite speed of signals transmitted over the network) combined with high transmission rates (a consequence of a desire to transmit as much information in the shortest time possible) conspire to create large delay-bandwidth product. Large delay-bandwidth products make traffic regulation on or control of the network difficult because: 1) at any given time a large amount of data is on the network (a consequence of the large bandwidth aspect of the network); 2) feedback signals describing the state of congestion on the network do not instantaneously reach the mechanisms that control network traffic (i.e. the propagation delay aspects); and 3) by the time the feedback signals arrive, additional data is already in transit. Thus, regulation information describing the state of the network is dated, and the controls triggered by the information can result in improper regulation of the network. Improper regulation can lead to the loss of large amounts of data on the network requiring costly and time-consuming retransmission. Additionally, traffic controls can be triggered which can lead to undesirable oscillations in the traffic flow.
Existing algorithms for network traffic management are often based on packet-by-packet adaptation, precision arithmetic and implicit feedback. See generally, D. Mitra and J. B. Seery, "Dynamic Adaptive Windows for High Speed Data Networks: Theory and Simulations," Proc. ACM SIGCOMM, 30-40 (1990); D. Mitra and J. B. Seery, "Dynamic Adaptive Windows for High Speed Data Networks with Multiple Paths and Propagation Delays," Computer Networks and ISDN Systems, vol. 25, pp. 663-679 (1993); A. Mukherjee and J. C. Strikwerda, "Analysis of Dynamic Congestion Control Protocols--A Fokker-Planck Approximation," Proc. ACM SIGCOMM, pp. 159-169 (1991); and K. W. Fendick, M. A. Rodrigues and A. Weiss, "Analysis of Rate-Based Feedback Control Strategy for Long Haul Data Transport," Performance Evaluation, vol. 16, pp. 67-84 (1992).
However, new incentives to design other methods have arisen from the availability of a single bit for forward and backward explicit congestion notification, e.g., in the Asynchronous Transfer Mode (ATM) switching format for BISDN. The response-time based algorithms, modified by 1-bit explicit feedback, have been explored using the FCFS service discipline and have proved unsatisfactory in terms of "fairness" of bandwidth allocation between VCs. Excess bandwidth is not allocated fairly to the active VCs in either short-term or long-term. Also, typically, the start-up VC in the presence of established VCs with large bandwidth allocations finds it difficult to obtain its fair share. See, e.g., A. Mukherjee and J. C. Strikwerda, "Analysis of Dynamic Congestion Control Protocols--A Fokker-Planck Approximation," Proc. ACM SIGCOMM, pp. 159-169 (1991). Such forms of unfairness are unacceptable, not remedied by tinkering with the design parameters, and fundamentally rooted in the combination of the three features: packet-by-packet adaptation, 1-bit explicit feedback, and FCFS service discipline.
The fairness aspect is improved when the service discipline is changed from FCFS to WRR. This combination is fair to all VCs and gives exemplary performance in all other respects, particularly in responsiveness to changing traffic conditions. A large part of this is derived from the packet-by-packet adaptation, which allows rapid adaptation when the throughput is high. Unfortunately, this same feature is a liability when used in conjunction with the FCFS service discipline. A. Demers, S. Keshav and S. Shenker, "Analysis and Simulation of a Fair Queueing Algorithm," J. Internetworking Res. Experience, 3-26 (1990), and L. Zhang, "Virtual Clock: A New Traffic Control Algorithm for Packet Switching Network," Proc. ACM SIGCOMM, 19-29 (1990) are illuminating on the role of service disciplines, albeit in the feedback-free framework.
The FCFS service discipline has important advantages: first, memory is more efficiently shared and thus smaller buffer memory usually suffices; second, it is cheaper and simpler to implement. Therefore, there is a need for methods for congestion control which use the FCFS discipline in which, furthermore, processing capability requirements are reduced by adapting rates and windows periodically and relatively infrequently.
The weighted round-robin (WRR) discipline is harder and more expensive to implement. Nonetheless, it has major advantages which make it the discipline of choice for VCs in certain applications. These applications are typically those which require a guaranteed, high grade of service in terms of bandwidth and delay. Isolation from the rest of the network, which the WRR discipline provides, makes such guaranteed performance possible. Desirably, future high speed networks will exploit both the FCFS and WRR disciplines, with VCs requiring guaranteed high grade of service using WRR and other VCs sharing buffers and bandwidth using the FCFS discipline. See D. D. Clark, S. Shanker and L. Zhang, "Supporting Real-Time Applications in an Integrated Services Packet Network: Architecture and Mechanism", Proc. SIGCOMM '92, pp. 14-26, (1992).